import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/3 10:05
 * @description 哈希表
 */
public class Solution2 {
    class FreqStack {
        /**
         * 数出现的频率
         */
        Map<Integer, Integer> freq;
        /**
         * 同一频率下，用栈保存所有的数
         */
        Map<Integer, Stack<Integer>> group;
        int maxfreq;

        public FreqStack() {
            freq = new HashMap();
            group = new HashMap();
            maxfreq = 0;
        }

        public void push(int x) {
            int f = freq.getOrDefault(x, 0) + 1;
            freq.put(x, f);
            if (f > maxfreq) {
                maxfreq = f;
            }
            group.computeIfAbsent(f, z-> new Stack()).push(x);
        }

        public int pop() {
            int x = group.get(maxfreq).pop();
            freq.put(x, freq.get(x) - 1);
            if (group.get(maxfreq).size() == 0) {
                maxfreq--;
            }
            return x;
        }
    }
}
